class Solution {
    /**
     * 思路1:动态规划, 每支股票存在两种状态
     * 
     * 持有股票 d[i][0] = max(d[i-1][0], d[i-1][1]-prices[i])
     * 未持股票 d[i][1] = max(d[i-1][1], d[i-1][0]+prices[i]);
     */
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len == 0)
            return 0;
        int[][] d = new int[len][2];
        d[0][0] = -prices[0];

        for (int i = 1; i < len; i++) {
            d[i][0] = Math.max(d[i - 1][0], d[i - 1][1] - prices[i]);
            d[i][1] = Math.max(d[i - 1][1], d[i - 1][0] + prices[i]);
        }

        return d[len - 1][1];
    }
}
class Solution {
    /**
     * 思路2：
     *  上坡思想，由于买卖股票是没有限制的，所以把所有涨的股票买了
     *  
     *  例1: [1,3,6] --> (3-1)+(6-3) = (6-1)
     *  
     *  例2: [1,3,6,20] -->
     */
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len == 0)
            return 0;

        int ans = 0;
        for (int i = 1; i < len; i++) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }

        return ans;
    }
}